public class prog {

    public static int KMP(String str,String sub,int pos){
        if(str==null||sub==null){
            return -1;
        }
        int lenStr=str.length();
        int lenSub=sub.length();
        if(lenSub==0||lenStr==0){
            return -1;
        }
        if(pos<0||pos>=lenStr) {
            return -1;
        }
        int[] next=new int[lenSub];
        getNext(sub,next);
        int i=pos;
        int j=0;
        while(i<lenStr&&j<lenSub){
            if(j==-1||str.charAt(i)==sub.charAt(j)){
                i++;
                j++;
            }
            else{
                j=next[j];
            }
        }
        if(j>=lenSub){
            return i-j;
        }
        return -1;
    }
    public static void getNext(String sub,int[] next){
        next[0]=-1;
        next[1]=0;
        int i=2;
        int k=0;
        for(;i<sub.length();i++){
            if(k==-1||sub.charAt(k)==sub.charAt(i-1)){
                next[i]=k+1;
                k++;
                i++;
            }
            else{
                k=next[k];
            }
        }
    }
    public static void main(String[] args) {
        System.out.println(KMP("abcabcabcd","abcd",0));
        System.out.println(KMP("abcabcabcd","abcf",0));
        System.out.println(KMP("abcabcabcd","ab",0));

    }
//    public static int KMP(String str,String sub,int pos){
//        if(str==null||sub==null){
//            return -1;
//        }
//        int lenStr=str.length();
//        int lenSub=sub.length();
//        if(lenSub==0||lenStr==0){
//            return -1;
//        }
//        if(pos<0||pos>=lenStr) {
//            return -1;
//        }
//        int[] next=new int[lenSub];
//        getNext(sub,next);
//        int i=pos;
//        int j=0;
//        while(i<lenStr&&j<lenSub){
//            if(j==-1||str.charAt(i)==sub.charAt(j)){
//                i++;
//                j++;
//            }
//            else{
//                j=next[j];
//            }
//        }
//        if(j>=lenSub){
//            return i-j;
//        }
//        return -1;
//    }
//    public static void getNext(String sub,int[] next){
//        next[0]=-1;
//        next[1]=0;
//        int i=2;
//        int k=0;
//        for(;i<sub.length();i++){
//            if(k==-1||sub.charAt(k)==sub.charAt(i-1)){
//                next[i]=k+1;
//                k++;
//                i++;
//            }
//            else{
//                k=next[k];
//            }
//        }
//    }
//    public static void main(String[] args) {
//        System.out.println(KMP("abcabcabcd","abcd",0));
//        System.out.println(KMP("abcabcabcd","abcf",0));
//        System.out.println(KMP("abcabcabcd","ab",0));
//
//    }






//public class prog {
//    public static int KMP(String str,String sub,int pos){
//        if(str==null||sub==null){
//            return -1;
//        }
//        int lenStr=str.length();
//        int lenSub=sub.length();
//        if(lenSub==0||lenStr==0){
//            return -1;
//        }
//        if(pos<0||pos>=lenStr) {
//            return -1;
//        }
//        int[] next=new int[lenSub];
//        getNext(sub,next);
//        int i=pos;
//        int j=0;
//        while(i<lenStr&&j<lenSub){
//            if(j==-1||str.charAt(i)==sub.charAt(j)){
//                i++;
//                j++;
//            }
//            else{
//                j=next[j];
//            }
//        }
//        if(j>=lenSub){
//            return i-j;
//        }
//        return -1;
//    }
//    public static void getNext(String sub,int[] next){
//        next[0]=-1;
//        next[1]=0;
//        int i=2;
//        int k=0;
//        for(;i<sub.length();i++){
//            if(k==-1||sub.charAt(k)==sub.charAt(i-1)){
//                next[i]=k+1;
//                k++;
//                i++;
//            }
//            else{
//                k=next[k];
//            }
//        }
//    }
//    public static void main(String[] args) {
//        System.out.println(KMP("abcabcabcd","abcd",0));
//        System.out.println(KMP("abcabcabcd","abcf",0));
//        System.out.println(KMP("abcabcabcd","ab",0));
//
//    }








//    public static int BF(String str1,String str2){
//        if(str1==null||str2==null){
//            return -1;
//        }
//        int len1=str1.length();
//        int len2=str2.length();
//        if(len1==0||len2==0){
//            return -1;
//        }
//        int i=0;
//        int j=0;
//        while(i<len1&&j<len2){
//            if(str1.charAt(i)==str2.charAt(j)){
//                i++;
//                j++;
//            }
//            else{
//                i=i-j+1;
//                j=0;
//            }
//        }
//        if(j>=len2) {
//            return i - j;
//        }
//        return -1;
//    }
//    public static void main1(String[] args) {
//        System.out.println(BF("abcabcabcd","abcd"));
//    }
}












/**合并两个链表
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
//        ListNode slow=list1;
//        ListNode fast=list1;
//        for(int i=0;i<a-1;i++){
//            slow=slow.next;
//        }
//        for(int i=0;i<b+1;i++){
//            fast=fast.next;
//        }
//        ListNode cur=list2;
//        slow.next=list2;
//        while(cur.next!=null){
//            cur=cur.next;
//        }
//        cur.next=fast;
//        return list1;
//    }
//}









/**交换链表中的节点
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode swapNodes(ListNode head, int k) {
//        int count =0;
//        ListNode cur=head;
//        while(cur!=null){
//            count++;
//            cur=cur.next;
//        }
//        int len=count-k;
//        ListNode slow=head;
//        ListNode fast=head;
//        while(len>0){
//            len--;
//            fast=fast.next;
//        }
//        while(k>1){
//            k--;
//            slow=slow.next;
//        }
//        int tmp=slow.val;
//        slow.val=fast.val;
//        fast.val=tmp;
//        return head;
//    }
//}










///**环形链表 II
// * Definition for singly-linked list.
// * class ListNode {
// *     int val;
// *     ListNode next;
// *     ListNode(int x) {
// *         val = x;
// *         next = null;
// *     }
// * }
// */
//public class Solution {
//    public ListNode detectCycle(ListNode head) {
//        ListNode fast=head,slow=head;
//        while(true){
//            if(fast==null||fast.next==null){
//                return null;
//            }
//            fast=fast.next.next;
//            slow=slow.next;
//            if(slow==fast){
//                break;
//            }
//        }
//        fast=head;
//        while(fast!=slow){
//            fast=fast.next;
//            slow=slow.next;
//        }
//        return fast;
//    }
//}











/**重排链表
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public void reorderList(ListNode head) {
//        if(head==null||head.next==null||head.next.next==null){
//            return ;
//        }
//        ListNode fast=head.next;
//        ListNode slow=head;
//        while(fast!=null&&fast.next!=null){
//            fast=fast.next.next;
//            slow=slow.next;
//        }
//        ListNode prev=null,next=slow.next;
//        slow.next=null;
//        slow=next;
//        while(slow!=null){
//            next=slow.next;
//            slow.next=prev;
//            prev=slow;
//            slow=next;
//        }
//        ListNode cur1=head;
//        ListNode cur2=prev;
//        while(cur1!=null&&cur2!=null){
//            next=cur1.next;
//            cur1.next=cur2;
//            cur2=cur2.next;
//            cur1.next.next=next;
//            cur1=next;
//        }
//    }
//}












/**反转链表 II
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode reverseBetween(ListNode head, int left, int right) {
//        ListNode newhead=new ListNode(-1);
//        newhead.next=head;
//        ListNode prev=newhead;
//        for(int i=0;i<left-1;i++){
//            prev=prev.next;
//        }
//        ListNode cur=prev.next;
//        ListNode curnext;
//        for(int i=0;i<right-left;i++){
//            curnext=cur.next;
//            cur.next=curnext.next;
//            curnext.next=prev.next;
//            prev.next=curnext;
//        }
//        return newhead.next;
//    }
//}











/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode partition(ListNode head, int x) {
//        ListNode midhead=new ListNode(-1);
//        ListNode maxhead=new ListNode(-1);
//        ListNode mid=midhead;
//        ListNode max=maxhead;
//        while(head!=null){
//            if(head.val<x){
//                mid.next=head;
//                mid=head;
//            }
//            else{
//                max.next=head;
//                max=head;
//            }
//            head=head.next;
//        }
//        max.next=null;
//        mid.next=maxhead.next;
//        return midhead.next;
//    }
//}












/**删除排序链表中的重复元素 II
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode deleteDuplicates(ListNode head) {
//        ListNode newhead=new ListNode(-1);
//        newhead.next=head;
//        ListNode cur=newhead;
//        while(cur.next!=null&&cur.next.next!=null){
//            if(cur.next.val==cur.next.next.val){
//                int val=cur.next.val;
//                while(cur.next!=null&&val==cur.next.val)
//                {
//                    cur.next=cur.next.next;
//                }
//            }
//            else{
//                cur=cur.next;
//            }
//
//        }
//        return newhead.next;
//    }
//}











/**旋转链表，将链表形成环，再断开环，非常巧妙
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode rotateRight(ListNode head, int k) {
//        if(k==0||head==null||head.next==null){//检查链表
//            return head;
//        }
//        int len=1;//计算链表长度
//        ListNode cur=head;
//        while(cur.next!=null){//循环到最后一个节点，不要越过最后一个接节点
//            len++;
//            cur=cur.next;
//        }
//        int n=len-k%len;//总长度-（右移次数%总长度）=尾节点的位置。
//        if(n==len){//判断右移次数与总长度是否重合
//            return head;
//        }
//        cur.next=head;//将链表形成环链表
//        while(n-->0){//向后移动
//            cur=cur.next;
//        }
//        ListNode newhead=cur.next;//保存新的头
//        cur.next=null;//断开链表
//        return newhead;
//    }
//}









/**给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode swapPairs(ListNode head) {
//        ListNode newhead=new ListNode(-1);
//        newhead.next=head;
//        ListNode cur=newhead;
//        while(cur.next!=null&&cur.next.next!=null){
//            ListNode curnext1=cur.next;
//            ListNode curnext2=cur.next.next;
//            cur.next=curnext2;
//            curnext1.next=curnext2.next;
//            curnext2.next=curnext1;
//            cur=curnext1;
//        }
//        return newhead.next;
//    }
//}










/**链表两数相加
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        ListNode head=new ListNode(-1);//创建新链表的虚拟头节点
//        ListNode cur=head;
//        int num=0;
//        int tmp=0;
//        while(l1!=null||l2!=null){
//            int x=l1==null?0:l1.val;//如果有一个为空，访问就会造成错误，手动为0，
//            int y=l2==null?0:l2.val;
//            tmp=x+y+num;//加上前一位数是否进一
//            num=tmp/10;//两个值相加如果大于10进1
//            tmp=tmp%10;//获得当前两个数相加后的结果，如果大于10取个位
//            cur.next=new ListNode(tmp);//用两个数的和创建新的节点
//            cur=cur.next;//向后移动
//            if(l1!=null){//选择性的向后移动，防止越界错误error.
//                l1=l1.next;
//            }
//            if(l2!=null){
//                l2=l2.next;
//            }
//        }
//        if(num==1){
//            cur.next=new ListNode(num);//判断最后相加是否进1，选择再次生成一个节点。
//        }
//        return head.next;
//    }
//}
